import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class DisjointSets<T>
{
    private ArrayList<T> nodes;
    private ArrayList<T> parents;

	/**
	 * @param setItems
	 *            the initial items (sameSet and merge will never be called with
	 *            items not in this set, this set will never contain null
	 *            elements)
	 */
	public DisjointSets(Set<T> setItems)
    {
        this.nodes = new ArrayList<T>();
        this.parents = new ArrayList<T>();
		for( T node : setItems)
        {
            this.nodes.add(node);
            this.parents.add(node);
        }
	}

    public T findRoot(T node)
    {
       //if this node's parent is itself, then it is the root of this disjoint set
        int index = this.nodes.indexOf(node); // get the index of this node
        T parent = this.parents.get(index); //get this node's parent
        if(node.equals(parent))
        {
            return parent;
        }
        else
        {
            return findRoot(parent);
        }
    }

    public void pathCompression()
    {
        for(T node : this.nodes)
        {
            //set this node's parent to the root of this tree
            int index = nodes.indexOf(node);
            parents.set(index, this.findRoot(node));
        }
    }

	/**
	 * @param u
	 * @param v
	 * @return true if the items given are in the same set, false otherwise
	 */
	public boolean sameSet(T u, T v)
    {
        T parentU = this.findRoot(u);
        T parentV = this.findRoot(v);

		return parentU.equals(parentV);
    }

	/**
	 * merges the sets u and v are in, do nothing if they are in the same set
	 * You are required to implement the following in this method:
	 * 	Path compression: every node points to its root
	 *  Merge by rank: Let the rank (estimate tree depth) of each set initially be 0. 
	 *  When merging to set with different ranks, make the smaller ranked root point to the larger root.
	 *  If the two ranks are the same, choose one to point to the other, and increment the rank of the new set
	 *
	 * @param u
	 * @param v
	 */
	public void merge(T u, T v)
    {
        T parentU = this.findRoot(u);
        T parentV = this.findRoot(v);

        if(!parentU.equals(parentV))
        {
            int index = this.nodes.indexOf(parentV);
            this.parents.set(index, parentU);
        }
        this.pathCompression();
	}

    public boolean isMerged()
    {
        T curr = parents.get(0);
        for(int i =1; i <parents.size(); i++)
        {
            if(!curr.equals(parents.get(i)))
            {
                return false;
            }
        }
        return true;
    }

    private void printArrayList(ArrayList<Integer> arr)
    {
        for(Integer i : arr)
        {
            System.out.print(i+" ");
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        HashSet<Integer> data = new HashSet<Integer>();
        data.add(0);
        data.add(1);
        data.add(2);
        data.add(3);
        data.add(4);
        data.add(5);
        data.add(6);
        data.add(7);
        DisjointSets<Integer> mySet = new DisjointSets<Integer>(data);

        mySet.printArrayList(mySet.nodes);
        mySet.printArrayList(mySet.parents);

        mySet.merge(0,1);
//        mySet.merge(0,2);
//        mySet.merge(0,3);
//        mySet.merge(0,4);
//        mySet.merge(0,5);
//        mySet.merge(0,6);
        //mySet.merge(0,7);



//        int max = 100000;
//        Set<Integer> items = new HashSet<>();
//        for (int i = 0; i < max; i++) {
//            items.add(i);
//        }
//
//        DisjointSets<Integer> ds = new DisjointSets<>(items);
//        for (int incr = 2; incr < max; incr *= 2) {
//            System.out.println(incr);
//            for (int i = incr; i < max; i += incr) {
//                System.out.println(i +" "+ incr/2);
//                ds.merge(i - (incr / 2), i);
//            }
//        }
    }
}
